package com.test.sort;

import java.util.Arrays;
import java.util.Objects;

/**
 * 归并排序
 * @author sujiafa
 * @date 2024/8/13
 */
public class MergeSort {

    public int[] sortArray(int[] nums) {
        if (Objects.isNull(nums) || nums.length == 0) {
            return nums;
        }

        // 建立一个临时数组用来存放元素
        int[] temp = new int[nums.length];

        mergeSort(nums, temp, 0, nums.length - 1);

        return nums;
    }

    public void mergeSort(int[] nums, int[] temp, int low, int high) {

        if (low < high) {
            int middle = (low + high) / 2;
            // 对左边序列进行排序
            mergeSort(nums, temp, low, middle);
            // 对右边序列进行排序
            mergeSort(nums, temp, middle + 1, high);
            // 合并
            merge(nums, temp, low, middle, high);
        }
    }

    public void merge(int[] nums, int[] temp, int low, int middle, int high) {

        int i = 0;
        int j = low;
        int k = middle + 1;

        while (j <= middle && k <= high) {
            if (nums[j] <= nums[k]) {
                temp[i++] = nums[j++];
            } else {
                temp[i++] = nums[k++];
            }
        }

        // 将左边剩余的填充进来
        while (j <= middle) {
            temp[i++] = nums[j++];
        }
        // 将右边剩余的填充进来
        while (k <= high) {
            temp[i++] = nums[k++];
        }

        // 将临时数组中的元素拷贝到原数组中
        for (int t = 0; t < i; t++) {
            nums[low + t] = temp[t];
        }
    }

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        System.out.println(Arrays.toString(mergeSort.sortArray(new int[]{11, 44, 23, 67, 88, 65, 34, 48, 9, 12})));
    }
}
